package leetcode.回溯DFS;



public class Leetcode1510 {
    public boolean winnerSquareGame(int n) {
        Boolean[] dp = new Boolean[n+1];
        return dfs(n,dp);
    }

    public boolean dfs(int n,Boolean[] dp){
        if(n==1){
            return true;
        }
        if(dp[n] != null){
            return dp[n];
        }
        for(int i = (int)Math.sqrt(n);i>=1;i--){
            if(!dfs(n-i*i,dp)){
                return dp[n] = true;
            }
        }
        return dp[n] = false;
    }
}
